Задачи регрессии и классификации¶
Содержание¶
Метрические методы классификации¶
- Определение расстояний между объектами
- Обобщенный метрический классификатор
- KNN и его вариации
Байесвоская классификация¶
- Байесовский подход к классификации
- Наивный байесовский классификатор
Параметрические методы восстановления плотности¶
- Задача восстановления плотности распределения
- Восстановление многомерной гауссовой плотности
- Разделение смеси распределений, EM-алгоритм
Постановка задачи машинного обучения¶
$X \space-$ множество объектов
$Y \space-$ множество ответов
$y : X → Y \space-$ целевая функция
$X^\ell = \{(x_1, y_1), \ldots, (x_\ell, y_\ell)\} \space-$ обучающая выборка
$a : X → Y \space-$ алгоритм, решающая функция, приближающая значения целевой функции на множестве X
Модель алгоритма $-$ параметрическое семество функций $A = \{a(x, \theta) | \theta \in \Theta \} $
Функция потерь (loss function) $L(a(x), y) \space -$ величина ошибки алгоритма $a \in A$ на объекте $x \in X$
Эмпирический риск $-$ функционал качества алгоритма a на обучающей выборке $X^\ell$:
$$Q(a, X^{\ell}) = \frac{1}{\ell} \sum_{i=1}^{\ell} L(a(x_i),y_i)$$Метод обучения - минимизация эмпирического риска:
$$a= \mu(X^\ell) = \operatorname*{argmin}_{a \in A} Q(a, X^{\ell})$$Гипотезы непрерывности и компактности¶
Гипотеза непрерывности (для регрессии): близким объектам сооствествуют близкие ответы.
Гипотеза компактности (для классификации): близкие объекты как правило лежат в одном классе.
plot_blob()
Формализация понятия близости¶
Евклидова метрика и обобщенная метрика Миньковского:
$$\rho (x, x_i) = ( \sum_{j=1}^{n}|x^j - x_i^j|^2 )^\frac{1}{2}$$$$\rho (x, x_i) = ( \sum_{j=1}^{n}w_j|x^j - x_i^j|^p )^\frac{1}{p}$$$x = (x^1,\dots, x^n) - $ вектор признаков объекта $x$
$x_i = (x_i^n, \dots, x_i^n) - $ вектор признаков оъекта $x_i$
$w = (w_i, \dots, w_n) - $ веса признаков, которые можно обучать.
Эквидистантные поверхности при различных p¶
plot_minkowski()
<Figure size 700x400 with 0 Axes>
Расстояние между объектами¶
Расстояния между строками:
- расстояние левенштейна - минимальное количество односимвольных операций (вставки, удаления, замены), необходимых для превращения одной последовательности символов в другую.
- косинусная мера $\rho(x,y) = \frac{\langle x, y \rangle}{||x|| ||y||}$, где $x_i = \frac{c_i}{\sum c_j}$ - частота слова $с_i$ в документе
Расстояние между сигналами: $\rho(x,y) = \sqrt {\int_{a}^{b} (x(t)-y(t))^2 dt}$
Расстояние между изображениями: норма Фробениуса $\rho(x,y) = \sqrt {\sum_{i,j=1}^{m,n}|x_{i,j}-y_{i,j}|^2}$
Проклятье размерности¶
plot_curse()
C увеличение количества неинформативных признаков шумовая составяющая будет вносить решающую роль в метрику близости объектов.
Зависимость отношения стандартного отклонения объекта первого класса от своей центроиды к расстоянию между центроидами кластеров с ростом количества признаков:
Обобщенный метрический классификатор¶
Для произвольного $x \in X$ отранжируем объекты обучающей выборки $x_1,\dots, x_\ell$: $$ \rho(x,x^{(1)}) \le \rho(x,x^{(2)}) \le \dots \le \rho(x, x^{(\ell)}) $$
$x^{(i)} - $ i-й сосед объекта х среди $x_1, \dots, x_\ell $
$y^{(i)} - $ ответ на i-м соседе объекта х
Метрический алгоритм классификации:
$$a(x; X^\ell) = \operatorname*{argmax}_{y \in Y} \sum_{i=1}^\ell [y^{(i)} = y] w(i,x)$$$w(i, x) -$ вес (степень важности) i-го соседа объекта x
$\sum_{i=1}^\ell [y^{(i)} = y] w(i,x) - $ оценка близости объекта x к классу y
Метод k-ближайших соседей¶
$$a(x; X^\ell) = \operatorname*{argmax}_{y \in Y} \sum_{i=1}^\ell [y^{(i)} = y] w(i,x)$$$w(i,x) = [i \le 1] -$ метод ближайшего соседа
$w(i,x) = [i \le k] -$ метод k ближайших соседей
Преимущества:
- простота реализации (lazy learning)
- параметр k можно оптимизировать leave-one-out: $$LOO(k, X^\ell) = \sum_{i=1}^\ell[a(x_i; X^\ell \backslash {x_i}, k) \ne y_i] → \operatorname*{min}_k $$
Недостатки:
- возможна неоднозначность классификации при четном k
- не учитываются расстояния до объектов
Метод k взвешенных соседей¶
$w(i,x) = [i \le k] w_i$
где $w_i -$ вес, зависящий только от номера соседа
Возможные эвристики:
$w_i = \frac{k+1-i}{k} - $ линейное убывание весов
$w_i = q^i - $ экспоненциальное убывание весов
Проблемы:
- как обоснованно задать веса
- возможно, было бы лучше, если бы вес $w(i,x)$ зависел не от позиции в вариационном ряду, а от расстояния до него $\rho(x, x^{(i)})$
Убывание веса объекта¶
plot_weight()
Метод окна Парзена¶
$$w(i, x) = K ( \frac{h} {\rho(x,x^{i})} ) $$$h - $ где h - ширина окна,
$K(r) - $ ядро, не возрастает и положительно на [0,1]
Метод парезеновского окна фиксированной ширины:
$$a(x; X^\ell) = \operatorname*{argmax}_{y \in Y} \sum_{i=1}^\ell [y^{(i)} = y] K ( \frac{h}{\rho(x,x^{i})}) $$Метод парезеновского окна переменной ширины:
$$a(x; X^\ell) = \operatorname*{argmax}_{y \in Y} \sum_{i=1}^\ell [y^{(i)} = y] K ( \frac{\rho(x,x^{k+1})}{\rho(x,x^{i})} ) $$Гиперпараметры модели:
- ширина окна h и число соседей k
- выбор ядра K
Метод потенциальных функций¶
$$w(i, x) = q^{(i)} K ( \frac{1}{\rho(x,x^{i})})$$$ q^{(i)} -$ вес объектов, $\gamma \ge 0$
$$a(x; X^\ell) = \operatorname*{argmax}_{y \in Y} \sum_{i=1}^\ell [y^{(i)} = y] q^{(i)} \frac{1}{\rho(x,x^{i})^2} $$Физическая аналогия из электростатики:
$ q^{(i)} -$ величина "заряда" в точке $x_i$
$E(x, x_i) = q^{(i)}K(x, x_i) = \frac{q^{(i)}k}{\rho(x,x^{(i)})^2} - $ напряженность поля в точке x, создаваемая зарядом $q^{i}$
$y_i$ - знак "заряда" (в случае двух классов $y = \{-1, +1\}$
Метод потенциальных функций и линейный классификатор¶
Для задачи бинарной классификации $y = \{-1, +1\}$ $$a(x; X^\ell) = sign \sum_{i=1}^\ell y^{(i)} q^{(i)} K ( \frac{k}{\rho(x,x^{i})^2} ) $$
Сравним с линейной моделью классификации:
$$a(x) = sign \sum_{j=1}^n q^{(j)} f_j(x) $$$f_j(x) = y^{(j)} K ( \frac{k}{\rho(x,x^{j})^2} ) - $ новые признаки объекта x
$ q^{(i)} - $ веса линейного классификатора
$n = \ell$ - число признаков равно числу обхектов в обучающей выборке
Профиль компактности¶
Профиль компактности выборки $X^\ell$ - это функция доли объектов $x_i$ у которых m-й сосед $x_i^{m}$ лежит в другом классе:
$$K(m, X^\ell) = \frac{1}{L}\sum_{i=1}^{\ell}[y_i \ne y_i^{(m)}] $$где $x_i^{(m)}$ - m-й сосед объекта $x_i$ среди $X^{\ell}$
$y_i^{(m)} - $ ответ на m-ом соседе объекта $x_i$
Метрический подход к регрессионной задаче, формула Надарая-Ватсона¶
$Y = \mathbb{R} \space -$ задача регрессии
$$a(x) = \frac {\sum_{i=1}^{\ell} y_i w_i(x)} {\sum_{i=1}^{\ell} w_i(x)}= \frac{ \sum_{i=1}^{\ell} y_i K( \frac{\rho(x,x^{i})}{h})}{ \sum_{i=1}^{\ell} K( \frac{\rho(x,x^{i})}{h})} $$Часто используемые ядра K(r)¶
$П(r) = [|r| \le 1] - $ прямоугольное
$T(r) = (1 - |r|)[|r| \le 1] - $ треугольное
$Q(r) = (1 - r^2)^2[|r| \le 1] - $ квадратичное
$G(r) = e^{-2r^2} - $ гауссовое
plot_kernels()
Метод поиска ближайших соседей¶
Если просто перебирать все объекты обучающей выборки, выбирая наиболее близкий к новому объекту, то получаем сложность $O(\ell k)$
- kd-tree (k-мерное дерево) - особый вид двоичных деревьев поиска
- locality-sensitive hashing (LSH) - hash-функция, близкие объекты имеют похожие хэши
KD-tree¶
plot_kdtree()
Для приближённого поиска можно перебирать только объекты в листе
Можно построить несколько деревьев со случайными разбиениями признакового пространства на подпространства
Резюме¶
Плюсы:
- Легко реализуемы
- Легко интерпретируемы
- Мало гиперпараметров:
- число ближайших соседей k или ширину окна h
- веса объектов
- набор эталонов
Минусы:
сложность классификации зависит от объёма обучающей выборки
требуется хранение всей обучающей выборки
требует тщательного подбора метрики
Байесовская теория классификации¶
Задача классификации: $ X \in \mathbb R^n$, $Y \in \{-1, +1\}$
Априорные вероятностные предположения:
Пусть $X \times Y$ - вероятностное пространство с плотностью $p(x,y)=P(y|x)p(x)$
Совместную плотность вероятности можно расписать двумя способами $$p(x,y)=P(y|x)p(x) = P(y)p(x|y)$$
$P(y) - $ априорная вероятность класса y
$p(x|y) - $ функция правдоподобия класса y
$P(y|x) - $ апостериорная вероятность класса y
Принцип максимума апостериорной вероятности: $$a(x) = \operatorname*{argmax}_{y \in Y} P(y|x) = \operatorname*{argmax}_{y \in Y} P(y) p(x|y)$$
Как получить эмпирические оценки $\hat{P}(y)$ и $\hat{p}(x|y)$ по обучающей выборке?
Принцип максимума апостериорной вероятности¶
$$a(x) = \operatorname*{argmax}_{y \in Y} p(x|y)$$при равных $P(y)$
plotly_plot_bivariate_normal_pdf(*py_bivariate_normal_pdf(3,3,0.25))
Наивный байесовский классификатор¶
Признаки - независимые случайные величины с плотностями распределения $p_j(\xi|y)$, где $j \in 1,\dots, n$
Тогда функции прадвоподобия классов представимы в виде $p(x|y) = \overset{n} {\underset{j=1}{П}}p_j(\xi|y)$
Принцип максимума апостериорной вероятности: $$a(x) = \operatorname*{argmax}_{y \in Y} P(y) p(x|y) = P(y) \overset{n} {\underset{j=1}{П}}p_j(\xi|y)$$
$$a(x) = \operatorname*{argmax}_{y \in Y} ln \space P(y) + \overset{n} {\underset{j=1}{\sum}}ln \space p_j(\xi|y)$$Восстановление по обучающей выборке n одномерных плотностей класса намного проще, чем восстановление одной многомерной
Наивный байесовский классификатор¶
$$a(x) = \operatorname*{argmax}_{y \in Y} ln \space P(y) + \overset{n} {\underset{j=1}{\sum}}ln \space p_j(\xi|y)$$ $$a(x) = \operatorname*{argmax}_{y \in Y} ln \space P(y) + \overset{n} {\underset{j=1}{\sum}}ln \space p_j(\xi|y,\mu_j,\sigma_j)$$$p_j(\xi|y,\mu_j,\sigma_j)$ - одномерное нормальное распределениия признака $j$ со средним $\mu$ и дисперсией $\sigma$
Что делать если признаки распределены "ненормально"?
Нормализация распределения признаков, выбор более богатого параметрического семейства плотностей, чем нормальное.
Смеси распределений¶
$p(x)$ является смесью распределений если $$
p(x)
=
\sum_{k = 1}^{K} \pi_k p_k(x|\theta_k),
\qquad
\sum_{k = 1}^{K} \pi_k = 1,
\qquad
\pi_k \geq 0,
$$
где $p_k(x|\theta_k) - $ распределение компоненты смеси,
$\pi_k = P(k) -$ априорные вероятности компонент,
$K -$ число компонент.
Будем считать, что распределения компонент смеси принадлежат некоторому параметрическому семейству: $p_k(x) = \phi(x | \theta_k)$.
plot_mixt()
Задача восстановления смеси распределений¶
$$ p(x) = \sum_{k = 1}^{K} \pi_k p_k(x), \qquad \sum_{k = 1}^{K} \pi_k = 1, \qquad \pi_k \geq 0, $$Задача при фиксированном $K$,
имея простую (i. i. d.) выборку $X^\ell = \{x_1, \dots, x_\ell\} \sim p(x)$
оценить вектор параметров $(\pi, \theta) = (\pi_1, \dots, \pi_k, \theta_1, \dots, \theta_k)$
Максимизация правдоподобия выборки и EM-алгоритм¶
$$ \log p(X | \pi, \theta) = \log П_{i = 1}^{\ell} p(x_i | \pi, \theta) = \sum_{i = 1}^{\ell} \log \Biggl\{ \sum_{k = 1}^{K} \pi_k p(x_i | \theta_k) \Biggr\} → \operatorname*{max}_{\theta, \pi} $$При ограничениях на веса $\sum_{k = 1}^{K} \pi_k = 1, \pi_k \geq 0$
Итерационный алгоритм Expectaition-Maximization
Начальное приближение параметров $(\theta, \pi)$
Повторять
Оценка срытых переменных $Z=(z_{i,j}) , z_{i,j} = P(j|x_i)$
$Z =$ E-шаг$(\theta, \pi)$
Максимизация правдоподобия отдельно по компонентам:
$(\theta, \pi)$ = M-шаг($\theta, \pi, Z$)
Пока $\theta, \pi, Z$ не стабилизируются
Вероятностная интерпретация¶
E-шаг - это формула Байеса
$$z_{i,j} = P(j|x_i) = \frac{P(j)p(x_i|j)}{p(x_i)} = \frac{\pi_j p(x_i|\theta_j)}{p(x_i)} = \frac{\pi_j p(x_i|\theta_j)}{\sum_{k = 1}^{K} \pi_k p(x_i|\theta_k)} $$М-шаг - максимизация взвешенного правдоподобия с весами объектов $z_{i,j}$ для j-й компоненты смеси
$$ \theta_j = \operatorname*{argmax}_\theta \sum_{i = 1}^{\ell} z_{i,j} \log p(x_i | \theta_k) $$$$ \pi_j = \frac{1}{\ell} \sum_{i = 1}^{\ell} z_{i,j} $$EM-алгоритм¶
вход: $X^{l} = {x_1, \dots, x_\ell}, K$
выход: $(\theta_j, \pi_j)_{j=1}^K - $ параметры смеси распределений
Начальное приближение параметров $(\theta_j)_{j=1}^K , \pi_j= \frac{1}{K}$
Повторять
E-шаг (expectation): для всех $i=1,\dots, \ell, j=1,\dots, k$
$$z_{i,j} = \frac{\pi_j p(x_i|\theta_j)}{\sum_{k = 1}^{K} \pi_k p(x|\theta_k)} $$M-шаг (maximization): $j=1,\dots, k$
$$ \theta_j = \operatorname*{argmax}_\theta \sum_{i = 1}^{\ell} z_{i,j} \log p(x_i | \theta_k) $$$$ \pi_j = \frac{1}{\ell} \sum_{i = 1}^{\ell} z_{i,j} $$Пока $\theta, \pi, Z$ не стабилизируются
Дивергенция Кульбака-Лейблера¶
Мера "различия" распределений $p$ и $q$: $$ KL(p \| q) = \int p(z) \log \frac{p(z)}{q(z)} dz = \sum_{z \in Z} P(z) \log \frac{P(z)}{Q(z)} $$ где Z - множество полученное дискритизацией значений непрерывной случайной величины
plot_kl()
